public class test {
    //leetcode 18.四数之和
    class Solution {
        public List<List<Integer>> fourSum(int[] nums, int target) {
            List<List<Integer>> list = new ArrayList<>();
            Arrays.sort(nums);
            int len = nums.length;
            for (int n = 0; n < len - 3; n++) {
                if (n > 0 && nums[n - 1] == nums[n]) {
                    continue;
                }
                int i = n + 1;
                while (i < len - 2) {
                    if (i > n + 1 && nums[i - 1] == nums[i]) {
                        i++;
                        continue;
                    }
                    int j = i + 1;
                    int k = len - 1;
                    while (j < k) {
                        // 去重操作
                        if (j - 1 != i && nums[j] == nums[j - 1]) {
                            j++;
                            continue;
                        } else if (k + 1 != len && nums[k] == nums[k + 1]) {
                            k--;
                            continue;
                        }
                        long i1 = (long)target - nums[n] - nums[i];
                        long i2 = (long)nums[j] + nums[k];
                        if (i2 > i1) {
                            k--;
                        } else if (i2 < i1) {
                            j++;
                        } else {
                            List<Integer> list0 = new ArrayList<>();
                            list0.add(nums[n]);
                            list0.add(nums[i]);
                            list0.add(nums[j]);
                            list0.add(nums[k]);
                            list.add(list0);
                            k--;
                            j++;
                        }
                    }
                    i++;
                }
            }
            return list;
        }
    }
    //leetcode 长度最小的子数组
    class Solution {
        public int minSubArrayLen(int target, int[] nums) {
            int left = 0;
            int right = 0;
            int len = Integer.MAX_VALUE;
            int sum = 0;
            while(right < nums.length) {
                sum += nums[right];
                while(sum >= target) {
                    len = Math.min(len,right - left + 1);
                    sum -= nums[left];
                    left++;
                }
                right++;
            }
            return len == Integer.MAX_VALUE ? 0 : len;
        }
    }
    //leetcode 34.在排序数组中查找元素的第一个和最后一个位置
    class Solution {
        public int[] searchRange(int[] nums, int target) {
            if(nums.length == 0){
                return new int[]{-1,-1};
            }
            return new int[] { searchLeft(nums, target), searchRight(nums, target) };
        }

        public int searchLeft(int[] arr, int num) {
            int left = 0;
            int right = arr.length - 1;
            while (left < right) {
                int mid = left + (right - left) / 2;
                if (arr[mid] < num) {
                    left = mid + 1;
                } else if (arr[mid] >= num) {
                    right = mid;
                }
            }
            if (arr[left] == num) {
                return left;
            }
            return -1;
        }

        public int searchRight(int[] arr, int num) {
            int left = 0;
            int right = arr.length - 1;
            while (left < right) {
                int mid = left + (right - left + 1) / 2;
                if (arr[mid] <= num) {
                    left = mid;
                } else if (arr[mid] > num) {
                    right = mid - 1;
                }
            }
            if (arr[left] == num) {
                return left;
            }
            return -1;
        }
    }
    //leetcode 69.x的平方根
    class Solution {
        public int mySqrt(int x) {
            long left = 0;
            long right = x;
            while(left < right){
                long mid = left + (right - left + 1) / 2;
                if(mid * mid <= x){
                    left = mid;
                }else if(mid * mid > x){
                    right = mid - 1;
                }
            }
            return (int)left;
        }
    }
}
